﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;


namespace Hoshimi._TSP_
{
    public class TSP_BFS
    {
        TSPnode root;
        public int nodesSearched = 0;
        public TSPnode solutionNode;
        public int tourSumDistance = 0;
		protected Graph<TSPnode> graph = null;

        public TSP_BFS(TSPnode rootP)
        {
            root = rootP;
        }

        public int nodeCompare(TSPnode first, TSPnode second)
        {
            return first.CompareTo(second);
        }

        public void solveBeam(int cutoff)
        {
            tourSumDistance = 0;
            solutionNode = null;
            nodesSearched = 0;

            graph = new Graph<TSPnode>(root, nodeCompare, cutoff);
            foreach (TSPnode node in graph.beam())
            {
                nodesSearched++;

                if (node.citiesLeft.Count == 0) //last node
                {
                    solutionNode = node;
                    
					// On ne retourne pas au départ !
					tourSumDistance = solutionNode.sumDistToRoot;
                }
            }
        }

		public List<TSPnode> GetTSPNodePath(TSPnode _node)
		{
			if (_node == null)
			{
				return null;
			}

			List<TSPnode> nodeList = new List<TSPnode>();
			
			TSPnode node	= _node;
			while (node.parent != null)
			{
				nodeList.Insert(0,node);
				node = node.parent;
			}

			return nodeList;
		}

		public List<Point> GetPointsPath(TSPnode _node, bool reversePath)
		{
			if (_node == null)
			{
				return null;
			}

			List<Point> pointList = new List<Point>();
			
			TSPnode node	= _node;
			while (node.parent != null)
			{
				if(node.thisCity == null)
				{
					continue;
				}
				if(reversePath)
				{
					pointList.Add(node.thisCity.mLocation);
				}
				else
				{
					pointList.Insert(0,node.thisCity.mLocation);
				}
				node = node.parent;
			}

			return pointList;
		}

		// On retire des bouts au chemin pour qu'il coute ce que l'on veut :)
		public List<TSPnode> FindBestPath(TSPnode _node, int maxCost, out int newCost)
		{
			if (_node == null)
			{
				newCost = 0;
				return null;
			}

			List<TSPnode> nodeList = new List<TSPnode>();
			
			TSPnode node = _node;
			int totalCost = node.sumDistToRoot;
			while (node != null && node.sumDistToRoot > 0)
			{
				nodeList.Add(node);
				node = node.parent;
			}
			

			int cost;
			int cost2;

			// On retire soit le début soit la fin du chemin en fonction du plus avantageux
			while (nodeList.Count > 1 && totalCost > maxCost)
			{
				cost	= nodeList[1].thisCity.Distance(nodeList[0].thisCity);
				cost2	= nodeList[nodeList.Count-2].thisCity.Distance(nodeList[nodeList.Count-1].thisCity);

				if (cost > cost2)
				{
					nodeList.RemoveAt(0);
					totalCost -= cost;
				}
				else
				{
					nodeList.RemoveAt(nodeList.Count-1);
					totalCost -= cost2;
				}
			}

			newCost = totalCost;

			return nodeList;
		}

		public List<TSPnode> FindBestPath2(TSPnode _node, int maxCost, out int newCost)
		{
			if (_node == null)
			{
				newCost = 0;
				return null;
			}

			List<TSPnode> nodeList = new List<TSPnode>();
			
			TSPnode node = _node;
			int totalCost = node.sumDistToRoot;
			while (node != null && node.sumDistToRoot > 0)
			{
				nodeList.Add(node);
				node = node.parent;
			}

			while (nodeList.Count > 2 && totalCost > maxCost)
			{
				int cost		= 0;
				int bestCost	= 0;
				int bestNode	= 0;
				int max			= nodeList.Count - 1;
				for (int i = 1; i < max; i++)
				{
					cost = nodeList[i - 1].thisCity.Distance(nodeList[i].thisCity);
					cost += nodeList[i].thisCity.Distance(nodeList[i + 1].thisCity);
					cost -= nodeList[i - 1].thisCity.Distance(nodeList[i + 1].thisCity);

					if (cost > bestCost)
					{
						bestCost = cost;
						bestNode = i;
					}
				}

				nodeList.RemoveAt(bestNode);

				totalCost -= cost;
			}

			newCost = totalCost;

			return nodeList;
		}

		public List<TSPnode> FindBestPath3(TSPnode _node, int maxCost, out int newCost)
		{
			if (_node == null)
			{
				newCost = 0;
				return null;
			}

			List<TSPnode> nodeList = new List<TSPnode>();
			
			TSPnode node = _node;
			int totalCost = node.sumDistToRoot;
			while (node != null && node.sumDistToRoot > 0)
			{
				nodeList.Add(node);
				node = node.parent;
			}
			

			int cost;
			int cost2;
			int cost3 = 0;

			// On retire soit le début soit la fin du chemin en fonction du plus avantageux
			while (nodeList.Count > 2 && totalCost > maxCost)
			{
				cost	= nodeList[1].thisCity.Distance(nodeList[0].thisCity);
				cost2	= nodeList[nodeList.Count-2].thisCity.Distance(nodeList[nodeList.Count-1].thisCity);

				int bestCost	= 0;
				int bestNode	= 0;

				int max			= nodeList.Count - 1;
				for (int i = 1; i < max; i++)
				{
					cost3 = nodeList[i - 1].thisCity.Distance(nodeList[i].thisCity);
					cost3 += nodeList[i].thisCity.Distance(nodeList[i + 1].thisCity);
					cost3 -= nodeList[i - 1].thisCity.Distance(nodeList[i + 1].thisCity);

					if (cost3 > bestCost)
					{
						bestCost = cost3;
						bestNode = i;
					}
				}
				if (cost3 < cost || cost3 < cost2)
				{
					if (cost > cost2)
					{
						nodeList.RemoveAt(0);
						totalCost -= cost;
					}
					else
					{
						nodeList.RemoveAt(nodeList.Count - 1);
						totalCost -= cost2;
					}
				}
				else
				{
					nodeList.RemoveAt(bestNode);
					totalCost -= cost3;
				}
			}

			newCost = totalCost;

			return nodeList;
		}
    }

    public class TSPnode: IGNode<TSPnode>, IComparable<TSPnode>
    {
        public City thisCity;
        public IList<City> citiesLeft;  //after thisCity removed
        int indx = -1;                  //into parents list of citiesLeft. 
                                       //-1 means this is the root node
        public int sumDistToRoot   = 0;

        TSPnode theParent = null;

        public TSPnode(City cityP, IList<City> leftP, TSPnode parent)
        {
            thisCity	= cityP;
            citiesLeft	= leftP;
            theParent	= parent;
        }

        static List<City> cloneCities(TSPnode node)
        {
            List<City> cities = new List<City>(node.citiesLeft.Count);
			foreach (City c in node.citiesLeft)
			{
				cities.Add(c);
			}

            return cities;
        }

        public TSPnode nextSibling()
        {
            if (indx < 0)
                return null;  //this is the root; no sibs

            int newIndx = indx + 1;
            if (newIndx > parent.citiesLeft.Count - 1)
                return null;

            List<City> cities = cloneCities(parent);
            City aCity = cities[newIndx];
            cities.RemoveAt(newIndx);
            TSPnode sib = new TSPnode(aCity, cities, parent);
            sib.indx = newIndx;
            sib.sumDistToRoot = parent.sumDistToRoot + sib.thisCity.Distance(parent.thisCity);

            return sib;
        }

        public TSPnode parent
        {
            get { return theParent; }
            set { theParent = value; }
        }

        public TSPnode firstChild()
        {
            if (citiesLeft.Count == 0)
                return null;

            List<City> cities = cloneCities(this);
            City aCity = cities[0];
            cities.RemoveAt(0);
            TSPnode child = new TSPnode(aCity, cities, this);
            child.indx = 0;
            child.sumDistToRoot = sumDistToRoot + child.thisCity.Distance(thisCity);

            return child;
        }

        #region IComparable<TSPnode> Members

        public int CompareTo(TSPnode other)
        {
            return this.sumDistToRoot.CompareTo(other.sumDistToRoot);
        }

        public bool Equals(TSPnode other)
        {
            if (other == this)
                return true;
            return this.CompareTo(other) == 0;
        }

        #endregion
    }
}
